/*
 * Project: a2
 * Copyright (C) 2008 ralfoide gmail com,
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

package com.alfray.a2.engine;



/**
 * This implements a circular buffer. Be forewarned that this circular
 * buffer as very peculiar semantics and is explicitly designed to be
 * used as the main storage for the ActionThread.
 * <p/>
 * This is <en>not</em> a general purpose collection class.
 * <p/>
 * The buffer contains a preallocated list of {@link IElement}.
 * Elements are never removed or added, they just get recycled.
 * When an element is done with, it is cleared.
 * <p/>
 * Pushing an element simply means incrementing the circular pointer.
 * If the maximum size is reached, {@link IndexOutOfBoundsException} is thrown.
 * This assume that unused elements are already in a "ready-to-use" state.
 * <p/>
 * The peek method simply returns the first element to be consumed, if any.
 * Nothing surprising here.
 * <p/>
 * The pop method is a bit more peculiar: it returns the first element, guaranteed
 * to be the same that the last peek would have given. But on top of that it
 * actually "detaches" the element from the buffer by replacing it by an
 * extra temporary one.
 * This means the caller can now push more element -- otherwise the next push
 * would modify the element currently popped.
 * When the next pop occurs, the detached element will be replaced in the buffer
 * to replace the newly detached element.
 * <p/>
 * With this design there are no allocations except the initial one and the growth
 * ones. The downside is that the caller can only hold to one popped element at
 * a time.
 */
public class CircularBuffer<T extends CircularBuffer.IElement> {

    public interface IElement {
        public void clear();
        public <E extends IElement> E clone();
        public <E extends IElement> E[] mkArray(int size);
    }

    private T[] mBuffer;
    private T   mExtra;

    /*
     * mBuffer is a circular buffer.
     * - first: first cell to read. -1 if nothing to read.
     * - last: last cell to read, included.
     *
     *
     * push: -1 0 > 0 0 > 0 1 ... > 0 N > 0 99
     * pop:  0 N > 1 N ... > N N > -1 0
     *
     * An overflow occurs when last==first after last++/loop.
     */

    private int mFirst;
    private int mLast;

    private final int mMaxSize;

    private final IElement mCreator;

    public CircularBuffer(IElement creator, int maxSize) {
        mCreator = creator;
        mMaxSize = maxSize;
        mExtra = creator.clone();
        init();
        reset();
    }

    private void init() {
        int n = mMaxSize < 16 ? mMaxSize : 16;
        mBuffer = mCreator.mkArray(n);
        alloc(mBuffer, 0, n - 1);
    }

    private void alloc(T[] buffer, int i, int j) {
        for (; i <= j; i++) {
            buffer[i] = mCreator.clone();
        }
    }

    /** Resets circular buffer but does not clear content. */
    public void reset() {
        mFirst = -1;
        mLast = 0;
    }

    /**
     * Resets the circular buffer of element and also clears every single
     * element.
     */
    public void clear() {
        reset();
        for (int i = 0; i < mBuffer.length; i++) {
            mBuffer[i].clear();
        }
    }

    /**
     * Prepares a new Action to be queued in the circular buffer.
     * <p/>
     * Must be called from a synchronized method.
     *
     * @return The new Action to fill.
     * @throws IndexOutOfBoundsException if there's a circular buffer overflow.
     */
    public T push() {
        if (mFirst == -1) {
            mFirst = mLast = 0;
        } else {
            mLast++;
            if (mLast == mBuffer.length) mLast = 0;
            if (mLast == mFirst) {
                return resize();
            }
        }
        return mBuffer[mLast];
    }

    private T resize() {
        if (mBuffer.length >= mMaxSize) {
            throw new IndexOutOfBoundsException("Circular buffer overflow, reached " +
                            Integer.toString(mMaxSize));
        } else {
            // Create a new buffer twice as large (or up to max size)
            int n = mBuffer.length * 2;
            if (n > mMaxSize) n = mMaxSize;
            T[] newBuf = mCreator.mkArray(n);

            // Copy mFirst..old_length to 0..N
            n = mBuffer.length - mFirst;
            System.arraycopy(mBuffer, mFirst, newBuf, 0, n);
            if (mLast > 0) {
                // Copy 0..mLast-1 to N..M
                System.arraycopy(mBuffer, 0, newBuf, n, mLast);
                n += mLast;
            }
            alloc(newBuf, n, newBuf.length);

            mBuffer = newBuf;
            mFirst = 0;
            mLast = n;

            return mBuffer[n];
        }
    }

    /**
     * Returns the first action to execute but does not remove it from the buffer.
     * Returns null if the queue is empty.
     * <p/>
     * Must be called from a synchronized method.
     */
    public T peek() {
        if (mFirst == -1) return null;
        return mBuffer[mFirst];
    }

    /**
     * Returns the first action and discard it, if any.
     * Returns null if the buffer is empty.
     * <p/>
     * The returned element is no longer stored in the queue.
     * The popped element is kept outside of the queue, and it will
     * be recycled by the next pop. This way the caller can use this
     * element without fear of it being modified by the next {@link #push()}.
     * This pattern works as long as only one pop is "pending" at a time.
     * <p/>
     * The caller must call {@link #recycle(T)} on the element.
     * <p/>
     * Must be called from a synchronized method.
     */
    public T pop() {
        if (mFirst == -1) return null;

        T popped = mBuffer[mFirst];
        mBuffer[mFirst] = mExtra;
        mExtra = popped;

        if (mFirst == mLast) {
            reset();
        } else {
            mFirst++;
            if (mFirst == mBuffer.length) mFirst = 0;
        }

        return popped;
    }

    /**
     * Recycles an element that has been returned by pop.
     * <p/>
     * This method does not need to be synchronized.
     */
    public void recycle(T element) {
        element.clear();
    }


}

